package task15;

import java.util.ArrayList;
import java.util.List;

public class MyHashMap<K,V> implements MyMap<K,V> {

    // 默认数组大小
    private static int defaultlength = 16;

    // 默认负载因子
    private static double defaultloader = 0.75;

    // Entry 数组
    private Entry<K,V>[] table = null;

    // HashMap 大小
    private int size = 0;

    // 自定义默认长度和负载因子
    public MyHashMap(int length, double loader){
        defaultlength = length;
        defaultloader = loader;
        table = new Entry[defaultlength];
    }

    // 使用默认值
    public MyHashMap() {
        this(defaultlength,defaultloader);
    }

    /*
    * 自定义哈希算法
    * 根据key的哈希值得到index索引，就是存放到数组中的下标
    * 返回的index值必须是一个正数
    * */
    private int getkey(K k) {
        int m = defaultlength;
        int index = k.hashCode() % m;
        return index >= 0 ? index : -index;
    }

    @Override
    public V put(K k, V v) {
        //判断size是否达到扩容标准
        if (size >= defaultlength * defaultloader) {
            expand();
        }

        //根据key和哈希算法算出数组下标
        int index = getkey(k);
        Entry<K,V> entry = table[index];
        //判断entry是否为空
        if(entry == null){
            /*
            * 如果entry为空，代表当前位置没有数据
            * new一个entry对象,内部存放key，value
            * 此时next指针没有值，因为这个位置上只有一个entry对象
            * */
            table[index] = new Entry(k,v,null);
            //map大小加1
            size++;
        }else{
            /*
            * 如果entry不为空,代表当前位置已经有数据了
            * new一个entry对象，内部存放key,value
            * 把next指针设置为原本的entry对象并且把数组中的数据替换为新的entry对象
            * */
            table[index] = new Entry<K,V>(k,v,entry);
        }
        return table[index].getValue();
    }

    @Override
    public V get(K k) {
        return null;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    class Entry<K,V> implements MyMap.Entry<K,V>{
        K k;
        V v;
        Entry<K,V> next;
        public Entry(K k, V v, Entry next) {
            this.k = k;
            this.v = v;
            this.next = next;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }
    }

    // 数组扩容方法
    private void expand() {
        //创建大小为原来两倍的entry数组
        Entry<K,V>[] newTable = new Entry[2*defaultlength];
        //重新散列
        rehash(newTable);
    }

    //重新散列的过程
    private void rehash(Entry<K,V>[] newTable) {
        //创建list用于装载HashMap
        List<Entry<K,V>> list = new ArrayList<Entry<K,V>>();

        //遍历整个数组
        for(int i = 0; i<table.length; i++) {
            if(table[i] == null){
                continue;
            }
            //通过递归将所有entry对象装载到list中
            findEntryByNext(table[i],list);
            if(list.size() > 0) {
                //重置size
                size = 0;
                //把默认长度设置为原来的两倍
                defaultlength = 2 * defaultlength;

                table = newTable;
                for (Entry<K,V> entry : list) {
                    if (entry.next != null) {
                        //把entry的next指针置空
                        entry.next = null;
                    }
                    System.out.println(size);
                    //对新table进行散列
                    put(entry.getKey(),entry.getValue());
                }
            }
        }
    }

    private void findEntryByNext(Entry<K,V> entry, List<Entry<K,V>> list){
        if(entry != null && entry.next != null) {
            list.add(entry);
            // 递归调用
            findEntryByNext(entry.next,list);
        }else {
            list.add(entry);
        }
    }

    /*
    * 通过递归比较key值的方式找到真正我们要找的value值
    * */
    public V findValueByEqualKey(K k, Entry<K,V> entry) {
        /*
        * 传进来的key如果等于entry的key，说明这个就是我们要的entry对象
        * 直接返回entry的value
        * */
        if (k == entry.getKey() || k.equals(entry.getKey())){
            return entry.getValue();
        }else {
            /*
            * 如果不相等，说明不是我们要找的entry对象
            * 通过递归方式比较next中entry的key值来找到真正的entry对象
            * */
            if (entry.next != null){
                return findValueByEqualKey(k,entry.next);
            }
        }
        return entry.getValue();
    }
}
